PGMS_155651_호텔 대실

그리디를 사용해서 호텔 객실의 최소 개수를 카운트하는 문제

입실 시간과 퇴실 시간을 int로 변환한 뒤 입실 시간이 빠른 것을 기준으로 정렬해줬다 그 후 우선순위 큐(방이라고 하자)를 만들었다 방은 퇴실 시간 + 10분의 정보를 담고 있고, 퇴실 빠른 순으로 정렬된다 예약 리스트를 돌면서 예약들을 offer() 해준다

맨 앞에 방(제일 빨리 퇴실함)에 들어갈 수 있으면 poll() 처리한다(헌 집 → 새 입주자)

못 들어가면 뒤에 있는 방도 못들어가기는 매한가지이기 때문에 새집을 얻은 것이다

삽질

그리디가 가물가물 해서 퇴실로 정렬 했다가 틀렸다. 빨리 나가는 게 아니라 빨리 오는 순서대로 받아줘야 한다

처음에는 우선순위 큐 대신 리스트로 구현했는데 요소 바뀔 때마다 재정렬 해줘야 해서 우선순위 큐로 바꿨다

Comparator 메소드 이름 : compare

Comparable 메소드 이름 : compareTo

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        // 이 익숙한 전개는 그리디...?
        
        List<int[]> bookingList = new ArrayList<>();
        
        for(int i = 0; i < book_time.length; i ++) {
            StringBuilder sb = new StringBuilder(book_time[i][0]);
            int hour = Integer.parseInt(sb.substring(0, 2));
            int min = Integer.parseInt(sb.substring(3, 5));
            int enterTime = hour * 60 + min;
            
            sb = new StringBuilder(book_time[i][1]);
            hour = Integer.parseInt(sb.substring(0, 2));
            min = Integer.parseInt(sb.substring(3, 5));
            int leaveTime = hour * 60 + min;
            
            bookingList.add(new int[] {enterTime, leaveTime});
        }
        
        Collections.sort(bookingList, new Comparator<int[]>() {
            
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
            
        Queue<Integer> rooms = new PriorityQueue<>(Comparator.naturalOrder());
        
        for(int[] booking : bookingList) {
            if(!rooms.isEmpty() && rooms.peek() <= booking[0]) {
                rooms.poll();
            }

            rooms.offer(booking[1] + 10);
        }
        
        return rooms.size();
    }
}